package com.ming.learn.from.carl.binary.tree;

import com.ming.commons.utils.TreeNode;
import com.sun.jmx.remote.internal.ArrayQueue;

import java.util.Stack;

/*
101. 对称二叉树
 */
public class Of20210307LeetCode101 {
    /*
    给定一个二叉树，检查它是否是镜像对称的。
     */
    public static void main(String[] args) {
        System.out.println(isSymmetric2(new TreeNode(1, new TreeNode(2, new TreeNode(3), new TreeNode(4)),
                new TreeNode(2, new TreeNode(4), new TreeNode(3)))));
    }

    /*
    递归法
     */
    private static boolean compare(TreeNode left, TreeNode right) {
        // 首先排除空节点的情况
        if (left == null && right != null) return false;
        else if (left != null && right == null) return false;
        else if (left == null && right == null) return true;
            // 排除了空节点，再排除数值不相同的情况
        else if (left.val != right.val) return false;
        // 此时就是：左右节点都不为空，且数值相同的情况
        // 此时才做递归，做下一层的判断
        return compare(left.left, right.right) && compare(left.right, right.left);
    }

    private static boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return compare(root.left, root.right);
    }

    /*
    迭代法
     */
    private static boolean isSymmetric2(TreeNode root) {
        if (root == null) return true;
        ArrayQueue<TreeNode> que = new ArrayQueue<>(10);
        que.add(root.left);   // 将左子树头结点加入队列
        que.add(root.right);  // 将右子树头结点加入队列
        while (!que.isEmpty()) {  // 接下来就要判断这这两个树是否相互翻转
            TreeNode leftNode = que.remove(0);
            TreeNode rightNode = que.remove(0);
            if (leftNode == null && rightNode == null) {  // 左节点为空、右节点为空，此时说明是对称的
                continue;
            }

            // 左右一个节点不为空，或者都不为空但数值不相同，返回false
            if ((leftNode == null || rightNode == null || (leftNode.val != rightNode.val))) {
                return false;
            }
            que.add(leftNode.left);   // 加入左节点左孩子
            que.add(rightNode.right); // 加入右节点右孩子
            que.add(leftNode.right);  // 加入左节点右孩子
            que.add(rightNode.left);  // 加入右节点左孩子

        }
        return true;
    }

    /*
    使用栈
    其实是把左右两个子树要比较的元素顺序放进一个容器，然后成对成对的取出来进行比较，那么其实使用栈也是可以的。
     */
    private static boolean isSymmetric3(TreeNode root) {
        if (root == null) return true;
        Stack<TreeNode> st = new Stack<>();
        st.push(root.left);
        st.push(root.right);
        while (!st.empty()) {
            TreeNode leftNode = st.pop();
            TreeNode rightNode = st.pop();
            if (leftNode==null && rightNode==null) {
                continue;
            }
            if ((leftNode==null || rightNode==null || (leftNode.val != rightNode.val))) {
                return false;
            }
            st.push(leftNode.left);
            st.push(rightNode.right);
            st.push(leftNode.right);
            st.push(rightNode.left);
        }
        return true;
    }
}
